package com.test.daily.leetcode.y2022.m05.day0529.v01;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/29 下午 07:36
 * @version: 1.0
 */
public class Code03_TopologicOrderDFS1 {
    public static class   DirectedGraphNode{
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;
        public DirectedGraphNode(int label){
            this.label = label;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }
    public static class Record{
        public int deep;
        public DirectedGraphNode node;
        public Record(DirectedGraphNode node, int deep){
            this.node = node;
            this.deep = deep;
        }
    }
    public static class TopSortedComparator implements Comparator<Record>{

        @Override
        public int compare(Record o1, Record o2) {
            return o2.deep - o1.deep;
        }
    }
    public static ArrayList<DirectedGraphNode> topSortedBFS(ArrayList<DirectedGraphNode> graph){
         HashMap<DirectedGraphNode, Record> order = new HashMap<>();
         for(DirectedGraphNode cur: graph){
             f(cur, order);
         }
        ArrayList<Record> recordArr = new ArrayList<>();
         for(Record r: order.values()){
             recordArr.add(r);
         }
         recordArr.sort(new TopSortedComparator());
         ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
         for(Record r: recordArr){
             ans.add(r.node);
         }
         return ans;
    }
    public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order){
        if(order.containsKey(cur)){
            return order.get(cur);
        }
        int follow = 0;
        for(DirectedGraphNode next: cur.neighbors){
            follow = Math.max(follow, f(next, order).deep);
        }
        Record ans = new Record(cur, follow + 1);
        order.put(cur, ans);
        return ans;
    }
}
